// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-19 15:29
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.Hash;

import java.util.HashMap;
import java.util.Map;

@SuppressWarnings("ALL")
public class LFUCache {
    private int capacity;
    Node hh, tt;
    Map<Integer, Node> map = new HashMap<>();

    class Node {
        // 双链表节点
        Node l, r;
        Node hh = new Node(-1);
        Node tt = new Node(-1);
        Map<Integer, Node> nodeMap = new HashMap<>();
        int cnt = 0;
        // k,v分别对应索引和对应的值，用于节点链表元素的查找
        int k, v;

        public Node() {
        }

        public Node(int cnt) {
            this.cnt = cnt;
        }
    }

    void clear(Node node) {
        /*
            实现空节点的清除，防止双向链表中出现空节点
         */
        if (node.hh.r == node.tt) {
            /*
                双向链表为空
             */
            node.l.r = node.r;
            node.r.l = node.l;
            node = null;
        }

    }


    public LFUCache(int capacity) {
        this.capacity = capacity;
        hh = new Node(-1);
        tt = new Node(-1);
        hh.r = tt;
        tt.l = hh;
    }

    public int get(int key) {
        /*
            获取节点信息，并且更新节点访问次数
         */
        if (map.containsKey(key)) {
            Node node = map.get(key);
            put(key, node.nodeMap.get(key).v);
            return node.nodeMap.get(key).v;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        Node next = null;
        /**
         *  节点内数据采用链表的方式进行存储的原因是因为需要从指定HashMap中删除最近最久未使用元素
         *  链表的下一个节点用于最久未使用节点的确定，链表的尾节点是最新插入的元素
         */
        if (map.containsKey(key)) {
            /*
                数据结构中存在该数据，需要增加该数据的访问次数，直接移动该节点，并且修改该节点信息即可
             */
            // 根据hash表定位节点所在位置
            Node node = map.get(key);
            /*
                根据节点内的hash表定位链表中节点的位置，然后修改元素信息
             */
            Node nd = node.nodeMap.get(key);
            if (node.r.cnt == node.cnt + 1) {
                //当前节点的右节点刚好是更新访问次数后的key元素所存放的位置
                next = node.r;
            } else {
                // 链表中不存在这样的节点
                next = new Node(node.cnt + 1);
                next.r = node.r;
                next.l = node;
                node.r.l = next;
                node.r = next;
            }
            nd.r = nd.l.r;
            nd.l = nd.r.l;
            nd.cnt += 1;
            nd.v = value;
            /*
                新插入的元素从链表尾部进行插入，不影响链表头部信息
             */
            nd.l = next.tt.l;
            nd = next.tt.l;
            nd.r = next.tt;
            /*
                更新索引信息
             */
            map.put(key, next);
            next.nodeMap.put(key, nd);
            /*
                一位从node节点中移除了一个节点，索引node节点可能会成为空节点
                空节点的判断是通过当前节点的双向链表是否为空进行判断
             */
            clear(node);
        } else {
            // 当前数据结构中不存在该元素信息，需要创建节点，如果容器容量不足还需要移除最久未使用的元素
            if (capacity <= 0) {
                // 容器空间不足，需要删除最近最久未使用节点,因为容器空间已经满了，说明链表中一定存在元素，而且需要考虑capacity == 0的情况
                /*
                    获取最久未访问节点并删除
                 */
                Node start = this.hh.r.hh;
                Node last = hh.r.hh.r;
                start.r = last.r;
                last.r.l = start;
                map.remove(last.k);
                hh.r.nodeMap.remove(last.k);
                clear(hh.r);
            }
            if (hh.r.cnt == 1) {
                // 第一个节点刚好可以存储新创建的节点
                next = hh.r;
            } else {
                next = new Node(1);
                next.r = hh.r;
                hh.r.l = next;
                hh.r = next;
            }
            Node nd = new Node();
            nd.k = key;
            nd.v = value;
            nd.r = next.hh.r;
            next.hh.r.l = nd;
            next.hh.r = nd;
            nd.l = hh;
            map.put(key, next);
            next.nodeMap.put(key, nd);
        }


    }


}
